package main.leetcode.clockin.September;

import main.datastruc.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 257. 二叉树的所有路径
 *
 * <p>给定一个二叉树，返回所有从根节点到叶子节点的路径。
 *
 * <p>说明: 叶子节点是指没有子节点的节点。
 */
public class day4 {
    private List<String> res;

    public static void main(String[] args) {
        TreeNode root = TreeNode.creCmpBTree(new int[] {1, 2, 3, 4, 5});
        System.out.println(new day4().binaryTreePaths(root));
    }

    public List<String> binaryTreePaths(TreeNode root) {
        res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        StringBuilder cur = new StringBuilder();
        dfs(root, cur);
        return res;
    }

    private void dfs(TreeNode root, StringBuilder cur) {
        int length = cur.length();
        if (length != 0) {
            cur.append("->");
        }
        cur.append(root.val);
        if (root.left == null && root.right == null) {
            res.add(cur.toString());
            cur.delete(length, cur.length());
            return;
        }
        if (root.left != null) {
            dfs(root.left, cur);
        }
        if (root.right != null) {
            dfs(root.right, cur);
        }
        cur.delete(length, cur.length());
    }
}
